package leetCode.offer36;

import java.util.ArrayList;
import java.util.List;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 *
 */
public class Solution1 implements Solution{


    @Override
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        List<Node> nodeList = new ArrayList<>();
        mSearch(root,nodeList);
        Node head = nodeList.get(0);
        for(int i=0;i<nodeList.size();i++){
            Node first = nodeList.get(i);
            Node second;
            if(i==nodeList.size()-1){
                second = nodeList.get(0);
            }else{
                second = nodeList.get(i+1);
            }
            first.right = second;
            second.left = first;
        }
        return head;
    }

    /**
     * 中序遍历
     * @param root
     */
    public void mSearch(Node root,List<Node> nodeList){
        if(root!=null){
            mSearch(root.left,nodeList);
            nodeList.add(root);
            mSearch(root.right,nodeList);
        }
    }

}
